For many years, workers have sought improvement in the automated solution of resource allocation problems. "Resource allocation problems", as used in this application, encompasses many different classes of problems. For example, a classical resource allocation problem is the so-called "traveling salesman" problem, wherein the question is to find the most efficient route to be taken by a traveling salesman through a series of stops, for example, all 48 state capitals of the continental United States. Additional constraints may include that no capital can be visited more than once, that the trip is to be accomplished using minimum total mileage, or the like. One way of solving this problem would be to compute all possible paths and simply to determine which had the least total mileage. However, as will be appreciated by those of skill in the art, there are so many possible paths that this problem is computationally very costly to solve using this "brute force" approach. Accordingly, the art has sought ways to simplify such problems.
Another class of resource allocation problems relates to the targeting of specified resources, such as weapons, towards specified goals, such as targets to be destroyed. The problem takes on additional complexities when it is realized that the likelihood of success of each weapon with respect to a particular target must be taken into account. Further, while the most reliable weapon may initially be targeted to the most important target, thus requiring evaluation of the relative importance of the targets in addition to reliability of the weapons, consideration of further constraints may also be necessary. For example, it may transpire that one of the targets cannot be successfully attacked other than with a single most effective weapon, meaning that another target, possibly the most important, must be attacked with less effective weapons if the overall solution is to be of value. As individual targets are hit, the relative priorities of the targets may change, depending on actual success ratios. A suitable mechanism for solving such a problem must also take into account multiple targeting of various weapons on the same targets to ensure their destruction, and other similar constraints. Defensive considerations must also be accounted for. Again, the "brute-force" approach of trying all possible solutions in order to select the most efficient is prohibitively costly in terms of the computation time and resources necessary.
The prior art has proposed solution of such complex problems using so-called "neural network" techniques. Neural networks may be considered to be sets of nodes connected by links, and may be realizable either physically or in computer software. Decisions are made based on plural weighted inputs to each node. The advantage of neural networks is generally considered to be that they "learn" in the sense that in a series of trials they can improve their performance, gradually approaching the optimal solution of a given problem. Numerous references describe neural networks both theoretically and their application to various practical problems, and additional references provide further improvements thereon. See generally U.S. Pat. Nos. 5,276,772 to Wang et al, 5,050,095 to Samad, 5,040,134 to Park, 5,222,195 to Alkon et al, and 5,276,771 to Manukian et al.
However, so far as known to the present inventor, no neural network solution is entirely satisfactory for solution of resource allocation problems as generally above, particularly in that the performance of neural networks degrades steeply when the constraints of a particular problem deviate from those initially learned by the network. Generally, performance gains obtained by a neural network's learning a solution to one problem do not carry over to another problem, requiring the network to be completely retrained. As resource allocation problems of a given class vary widely due to changes in the set of available resources, modification of allocation priorities, and other constraints, neural networks are not satisfactory for efficient solution of resource allocation problems.